bsearch() এর মাধ্যমে Binary Search

bsearch() এর মাধ্যমে Binary Search

সি প্রোগ্রামিং ভাষায় bsearch() ফাংশনটি একটি বিল্ট-ইন ফাংশন যা বাইনারি সার্চ (Binary Search) এলগরিদমের মাধ্যমে সॉর্ট করা অ্যারের মধ্যে একটি উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়। bsearch() ফাংশনটি stdlib.h হেডার ফাইলে ডিফাইন করা থাকে এবং এটি একত্রিতভাবে একটি স.sorted অ্যারে এবং একটি উপাদান অনুসন্ধান করতে সহায়ক।

বাইনারি সার্চ (Binary Search)

বাইনারি সার্চ একটি দ্রুত অনুসন্ধান পদ্ধতি যা সিলেক্ট করা তালিকায় উপাদান খুঁজে পেতে O(log n) সময়ে কাজ করে। এই পদ্ধতিতে, প্রথমে তালিকাটির মাঝের উপাদান পরীক্ষা করা হয়। তারপর, তালিকাটি দুটি ভাগে ভাগ করা হয় (যেমন, যদি কাঙ্ক্ষিত উপাদান ছোট হয়, তাহলে তালিকার বাম অংশে খোঁজা হয়, আর যদি বড় হয়, তাহলে ডান অংশে খোঁজা হয়) এবং এই প্রক্রিয়া পুনরাবৃত্তি করা হয় যতক্ষণ না উপাদানটি পাওয়া যায় বা তালিকার শেষ না হয়।

bsearch() ফাংশনের সিঙ্কট্যাক্স:

void *bsearch(const void *key, const void *base, size_t n_items, size_t size, int (*compar)(const void *, const void *));

আর্গুমেন্ট:

• key: এটি অনুসন্ধানযোগ্য উপাদান যা আপনি খুঁজছেন।
• base: এটি সসর্ড করা অ্যারের সূচক (pointer)।
• n_items: অ্যারে এর মধ্যে উপাদানের সংখ্যা।
• size: প্রতিটি উপাদানের আকার (বাইটে)।
• compar: একটি কাস্টম কম্প্যারিজন ফাংশন যা দুটি উপাদান তুলনা করতে ব্যবহৃত হয়।

রিটার্ন ভ্যালু:

• যদি উপাদানটি পাওয়া যায়, তবে bsearch() ফাংশনটি একটি পয়েন্টার রিটার্ন করবে যা সেই উপাদানের অবস্থান নির্দেশ করে।
• যদি উপাদানটি পাওয়া না যায়, তবে এটি NULL রিটার্ন করবে।

উদাহরণ: bsearch() ব্যবহার করে Binary Search

এখানে একটি উদাহরণ দেওয়া হলো, যেখানে bsearch() ফাংশন ব্যবহার করে একটি সসর্ড অ্যারের মধ্যে একটি উপাদান খোঁজা হয়েছে।

#include <stdio.h>
#include <stdlib.h>

// তুলনা ফাংশন যা bsearch() এর জন্য প্রয়োজন
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);  // দুটি ইন্টিজার তুলনা
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;
    
    // bsearch() ফাংশন ব্যবহার করে উপাদান খোঁজা
    int *result = (int *)bsearch(&key, arr, n, sizeof(int), compare);

    if (result != NULL) {
        printf("Element found: %d\n", *result);  // উপাদান পাওয়া গেলে তার মান প্রদর্শন
    } else {
        printf("Element not found\n");  // উপাদান না পাওয়া গেলে
    }

    return 0;
}

ব্যাখ্যা:

1. arr[]: এটি সসর্ড করা অ্যারে যার মধ্যে 10টি উপাদান রয়েছে।
2. compare(): এটি একটি তুলনা ফাংশন যা দুটি উপাদানকে তুলনা করে। এটি bsearch() ফাংশনের জন্য প্রয়োজন, কারণ bsearch() সসর্ড করা অ্যারের মধ্যে একটি উপাদান খোঁজে এবং এটি জানাতে পারে যে কোন উপাদান ছোট, বড়, বা সমান।
3. bsearch(): এটি key (যা খুঁজে বের করতে হবে) এবং arr (সসর্ড করা অ্যারে) এর মধ্যে n (উপাদানের সংখ্যা) এবং sizeof(int) (প্রতিটি উপাদানের আকার) পাস করা হয়।
4. ফলস্বরূপ, যদি key অ্যারেতে পাওয়া যায়, তবে bsearch() তার অবস্থান নির্দেশকারী পয়েন্টার রিটার্ন করবে। অন্যথায়, এটি NULL রিটার্ন করবে।

আউটপুট:

Element found: 7

যেহেতু 7 অ্যারেতে আছে, তাই এটি সেই উপাদানটি রিটার্ন করবে।

সারসংক্ষেপ:

• bsearch() ফাংশনটি বাইনারি সার্চ পদ্ধতিতে একটি সসর্ড অ্যারে থেকে একটি উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়।
• এটি key (যে উপাদানটি খুঁজে বের করতে চান) এবং base (সসর্ড অ্যারে) সহ আরো কিছু আর্গুমেন্ট গ্রহণ করে।
• বাইনারি সার্চ একটি খুব কার্যকরী পদ্ধতি যখন অ্যারে সসর্ড থাকে, কারণ এটি O(log n) সময়ে কাজ করে।
• compare() ফাংশনটি bsearch() ফাংশনের জন্য প্রয়োজন, যা দুটি উপাদান তুলনা করতে ব্যবহৃত হয়।

bsearch() একটি শক্তিশালী এবং দক্ষ উপায় অ্যারের মধ্যে ত্রুটিমুক্তভাবে উপাদান খুঁজে বের করার জন্য।